package com.benben.springSecurity.weiwei;

import java.util.ArrayList;
import java.util.List;

public class Sort {
    //冒泡排序：每一堂将待排序中最大元素移到最后，剩下的为新的待排序序列
    public void bubbleSort(int array[]){
        int t=0;
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    t = array[j];
                    array[j] = array[j+1];
                    array[j+1] = t;
                }
            }
        }
    }
    //选择排序法：每一趟从待排序序列选择一个最小的元素放到已排好序的末尾，剩下的为待排序序列
    public void selectSort(int array[]){
        int t = 0;
        for(int i=0;i<array.length-1;i++){
            int index = i;
            for(int j=i+1;j<array.length;j++){
                if(array[index] > array[j]){
                    index = j;
                }
            }
            if(index != i){ //找到了比array[i]小的则与array[i]交换位置
                t = array[i];
                array[i] = array[index];
                array[index] = t;
            }
        }
    }
    //插入排序:将数组分为两部分，将后部分元素逐一与前部分元素比较，如果前部分元素比array[i]小，就将前部分元素往后移动
    //当没有比array[i]小的元素，即是合理位置，在此位置插入array[i]
    public void insertSort(int[] array){
        int i,j,t = 0;
        for(i=1;i<array.length;i++){
            if(array[i] < array[i-1]){
                t = array[i];
                for(j = i-1;j>=0 && t<array[j];j--){
                    array[j+1] = array[j]; //数组统一往后移动一个位置
                }
                array[j+1] = t;//插入array[i]
            }
        }
    }
    //快速排序：首先设置一个轴值pivot，然后以这个轴值为划分基准将待排序序列分为比pivot大和比pivot小的两部分，接下来将划分的
    //子序列进行快排，直到一个元素为止
    public void quickSort(int[] array,int left,int right){
        if(left > right){
            return;
        }
        //base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while(i!=j){
            //顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while(array[j] >= base && i < j){
                j--;
            }
            //再从左往右找，直到找到比base值大的数
            while(array[i] <= base && i<j){
                i++;
            }
            if(i<j){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //将基准数放到中间位置（基准数归位）
        array[left] = array[i];
        array[i] = base;
        //递归，继续向基准的左右两边执行和上面同样的操作
        quickSort(array,left,i-1);
        quickSort(array,i+1,right);
    }

}
